package com.itheima.datastructure.binarytree;


import java.util.Arrays;

/**
 * 根据前序+中序遍历结果构造二叉树
 */
public class E09Leetcode105 {

    /*
        preOrder = {1,2,4,3,6,7}
        inOrder = {4,2,1,6,3,7}

        根 1
            pre         in
        左  2,4         4,2
        右  3,6,7       6,3,7


        根 2
        左 4

        根 3
        左 6
        右 7
     */

    /**
     * 根据前序和中序遍历结果构造二叉树
     *
     * @param preOrder 前序
     * @param inOrder  中序
     * @return TreeNode
     */
    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
        if (preOrder.length == 0 || inOrder.length == 0) {
            return null;
        }
        //创建根节点
        int rootValue = preOrder[0];
        TreeNode root = new TreeNode(rootValue);

        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
                //中序：左子树   4,2   [0~~~i-1]
                int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
                //中序：右子树   6,3,7  [i+1~~~inOrder.length-1]
                int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);

                //前序：左子树  2,4  拷贝长度=inLeft的长度
                int[] preLeft = Arrays.copyOfRange(preOrder, 1, i + 1);
                //前序：右子树  3,6,7 拷贝长度=inRight的长度
                int[] preRight = Arrays.copyOfRange(preOrder, i + 1, preOrder.length);

                //构建左节点
                root.left = buildTree(preLeft, inLeft);
                //构建右节点
                root.right = buildTree(preRight, inRight);

                break;

            }
        }
        return root;
    }


    public static void main(String[] args) {
        int[] preOrder = {1, 2, 4, 3, 6, 7};
        int[] inOrder = {4, 2, 1, 6, 3, 7};
        TreeNode root = new E09Leetcode105().buildTree(preOrder, inOrder);
    }


}
